/*
 * @lc app=leetcode.cn id=721 lang=javascript
 *
 * [721] 账户合并
 *
 * https://leetcode-cn.com/problems/accounts-merge/description/
 *
 * algorithms
 * Medium (28.59%)
 * Likes:    26
 * Dislikes: 0
 * Total Accepted:    777
 * Total Submissions: 2.7K
 * Testcase Example:  '[["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]'
 *
 * 给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称
 * (name)，其余元素是 emails 表示该帐户的邮箱地址。
 * 
 * 
 * 现在，我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址，则两个帐户必定属于同一个人。请注意，即使两个帐户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户，但其所有帐户都具有相同的名称。
 * 
 * 合并帐户后，按以下格式返回帐户：每个帐户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。
 * 
 * 例子 1:
 * 
 * 
 * Input: 
 * accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John",
 * "johnnybravo@mail.com"], ["John", "johnsmith@mail.com",
 * "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
 * Output: [["John", 'john00@mail.com', 'john_newyork@mail.com',
 * 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary",
 * "mary@mail.com"]]
 * Explanation: 
 * ⁠ 第一个和第三个 John 是同一个人，因为他们有共同的电子邮件 "johnsmith@mail.com"。 
 * ⁠ 第二个 John 和 Mary 是不同的人，因为他们的电子邮件地址没有被其他帐户使用。
 * ⁠
 * 我们可以以任何顺序返回这些列表，例如答案[['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
 * ⁠
 * ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']]仍然会被接受。
 * 
 * 
 * 
 * 注意：
 * 
 * 
 * accounts的长度将在[1，1000]的范围内。
 * accounts[i]的长度将在[1，10]的范围内。
 * accounts[i][j]的长度将在[1，30]的范围内。
 * 
 * 
 */
/**
 * @param {string[][]} accounts
 * @return {string[][]}
 */

// 将邮件地址作为图节点, 将同一个用户的邮件节点连通, 通过深度优先遍历, 遍历的一个连通分量就是一个用户的所有邮件账户
// 构建图的时候, 将每个账户映射到对应的账户名
// var accountsMerge = function(accounts) {
//     let graph = {}
//     let email_to_name = {}
//     let res = []
//     for (let i = 0; i < accounts.length; i++) {
//         let name = accounts[i][0]
//         let emails = accounts[i].slice(1)
//         graph[emails[0]] = graph[emails[0]] || new Set()
//         email_to_name[emails[0]] = name
//         for (let j = 1; j < emails.length; j++) {
//             let email = emails[j]
//             graph[email] = graph[email] || new Set()

//             email_to_name[email] = name
//             graph[emails[0]].add(email)
//             graph[email].add(emails[0])
//         }
//     }
//     let visited = new Set()
//     for (let g in graph) {
//         if (!visited.has(g)) {
//             visited.add(g)
//             // let re = bfs(g)
//             let re = dfs(g)
//             res.push([email_to_name[g], ...re.sort()])
//         }
//     }
//     return res
    
//     function bfs (e) {
//         let r = [e]
//         for (let g of graph[e].values()) {
//             if (!visited.has(g)) {
//                 visited.add(g)
//                 let re = bfs(g)
//                 r = r.concat(re)
//             }
//         }
//         return r
//     }

//     function dfs (e) {
//         let q = [e]
//         let re = []
//         while (q.length) {
//             let tmp = q.pop()
//             re.push(tmp)
//             for (let g of graph[tmp].values()) {
//                 if (!visited.has(g)) {
//                     visited.add(g)
//                     q.push(g)
//                 }
//             }
//         }
//         return re
//     }
// };

// 并查集
var accountsMerge = function(accounts) {
    let f = {}
    // 输入输出: 集合编号
    function find(x) {
        if (!(x in f)) f[x] = x
        if (x !== f[x]) f[x] = find(f[x])
        return f[x]
    }
    // 将集合x合并到y集合
    function union(x, y) {
        f[find(x)] = find(y) // 
    }

    let lookUp = {}
    // 合并集合
    for (let i = 0; i < accounts.length; i++) {
        let emails = accounts[i].slice(1)
        emails.forEach(email => {
            if (email in lookUp) union(i, lookUp[email])
            else lookUp[email] = i // 同集合划分
        })
    }

    console.log(f)
    console.log(lookUp)

    let sets = {}

    for (let email in lookUp) {
        console.log('--->', email, find(lookUp[email]))
        let id = find(lookUp[email])
        sets[id] = sets[id] || []
        sets[id].push(email)
    }

    let res = []

    for (let s in sets) {
        res.push([accounts[s][0], ...sets[s].sort()])
    }

    return res
    // console.log(f)
    // console.log(lookUp)
    // console.log(sets)
    // console.log(res)
};

// let data = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
let data = [["John","A","B"],["John","A","C"],["Mary","D"],["John","E"]]
let re = accountsMerge(data)
// console.log(re)

